package interview.countones;

import java.io.*;
import java.util.*;

public class CountOnes {
    public void count() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numTestCases = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < numTestCases; i++) {
			long start, end;
			start = System.currentTimeMillis();
            long oneCount = 0;
            String line = br.readLine();
            StringTokenizer st = new StringTokenizer(line);
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            
			if ( A < B ) {
                int temp = A;
                A = B;
                B = temp;
            }
            
            int prev = A;          
            int prevOneCount = 0;
            while(prev != 0) {
                prev &= prev - 1;
                prevOneCount++;
            }
            
            oneCount += prevOneCount;
            
            prev = A;
            for(int j = A - 1; j >= B; j--) {
                int trailingZeros = 0;
                if (prev == 0) {
                    trailingZeros = 33;
                } else {
                    while((prev & 0x1) == 0) {
                        trailingZeros++;
                        prev >>= 1;
                    }
                }
                
                prev = j;
                prevOneCount += trailingZeros - 1;
                oneCount += prevOneCount;
            }
            
			end = System.currentTimeMillis();
            System.out.println(oneCount + ":" + (end - start));
        }
    }

    public void count2() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numTestCases = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < numTestCases; i++) {
			long start, end;
			start = System.currentTimeMillis();
            long oneCount = 0;
            String line = br.readLine();
            StringTokenizer st = new StringTokenizer(line);
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
			long temp;
			
			if(A > B) {
				int t = A;
				A = B;
				B = t;
			}
            
			if( A < 0) {
				temp = A;
				temp *= -32;
				oneCount += temp;
				A = (A + 1) * -1;
				oneCount -= helper(A);
			} else {
				oneCount -= helper(A - 1);
			}

			if(B < 0) {
				B++;
				temp = B;
				temp *= -32;
				oneCount -= temp;
				B = (B + 1) * -1;
				oneCount += helper(B);
			} else {
				oneCount += helper(B);
			}
            
			end = System.currentTimeMillis();
            System.out.println(oneCount + ":" + (end - start));
        }
    }

	public long helper(int x) {
		// x > 0
		if (x <= 0)
			return 0;

		long oneCount = 0;
		long temp = x;
		int i = 0;
		while(temp > 0) {
			temp >>= 1;
			i++;
		}

		while(i > 1) {
			temp = 1 << (i - 2);
			temp *= (i - 1);
			x -= 1 << (i - 1);
			oneCount += temp + 1 + x;
			if(x == 0)
				break;
			while((x & (1 << (i - 1))) == 0) {
				i--;
			}
		}

		if ((x & 0x1) > 0) {
			oneCount += 1;
		}

		return oneCount;
	}
}
